package ACwing.P3SearchandGraph.BFS;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

/**
 * @Date : 2023-04-02
 * @Description:845. 八数码
 * 把每一个状态描述为一个 序号，求初始状态到最终状态最短路径
 * 状态表示复杂   用字符串表示 直接“1234x5678"
 * 如何记录距离  如何模拟队列
 */
public class EightPuzzleProblem {
    static Scanner scanner = new Scanner(System.in);
    static List<String> q = new ArrayList<>();  //队列
    static HashMap<String, Integer> d = new HashMap<>(); //距离
    public static void main(String[] args) throws IOException {
        StringBuffer start= new StringBuffer();
        for (int i = 0; i < 9; i++) {
            start.append(scanner.next());
        }
        System.out.println(bfs(start));
   }
   static int bfs(StringBuffer start){
        String end="12345678x";  //终点
        q.add(0,start.toString());
        d.put(start.toString(),0); //初始
        int hh=0,tt=0;//模拟队列

       int [] dx={-1,0,1,0},dy={0,1,0,-1};//上右下左
       while (hh<=tt){
           String s = q.get(hh++);
           StringBuffer t = new StringBuffer(s); //出列

           int dis=d.get(s);  //当前状态的距离
           if(s.equals(end))
               return dis;//如果s是终点就结束

           //状态转移
           int k=t.indexOf("x");  //找到x的位置
           int x=k/3,y=k%3; //转换为 二维的下标

           for (int i = 0; i < 4; i++) {
                int a=x+dx[i],b=y+dy[i];  //与之交换 二维的位置
                if(a>=0&&b>=0&&a<3&&b<3){
                    //交换字母
                    char temp = t.charAt(k);
                    t.setCharAt(k,t.charAt(a*3+b));
                    t.setCharAt(a*3+b,temp);

                    //如果当前状态没有搜到过   记录当前状态
                    if(!d.containsKey(t.toString())){
                        d.put(t.toString(),dis+1);  //距离更新
                        q.add(++tt,t.toString());  //入队
                    }
                    //恢复当前状态
                     temp = t.charAt(k);
                    t.setCharAt(k,t.charAt(a*3+b));
                    t.setCharAt(a*3+b,temp);

           }

           }

       }
        //没有解法  返回-1
        return -1;

   }
}
